package main

import (
	"fmt"
)

/**
执行用时：136 ms, 在所有 Go 提交中击败了64.26%的用户
内存消耗：4 MB, 在所有 Go 提交中击败了19.02%的用户
 */

type Node struct {
	id int
	son [26]*Node
}

func Constructor() *Node {
	res := &Node{}

	res.id = -1
	for i := 0; i < 26; i++ { res.son[i] = nil }

	return res
}

var root *Node
var ids map[int]int  // 会导致未初始化, 函数中必须初始化
var g [][]byte
var dx = []int{-1, 0, 1, 0}
var dy = []int{0, 1, 0, -1}

func findWords(board [][]byte, words []string) []string {

	g = board
	ids = make(map[int]int, 0)
	root = Constructor()
	for i := 0; i < len(words); i++ { insert(words[i], i) }

	for i := 0; i < len(g); i++ {
		for j := 0; j < len(g[0]); j++ {
			u := g[i][j] - 'a'
			if root.son[u] != nil {
				dfs(i, j, root.son[u])
			}
		}
	}

	res := []string{}
	for id := range ids {
		res = append(res, words[id])
	}
	return res
}

func dfs(x int, y int, p *Node) {

	if p.id != -1 { ids[p.id] = 0 }

	t := g[x][y]
	g[x][y] = '.'
	for i := 0; i < 4; i++ {
		a, b := x + dx[i], y + dy[i]
		if a >= 0 && a < len(g) && b >= 0 && b < len(g[0]) && g[a][b] != '.' {
			u := g[a][b] - 'a'
			if p.son[u] != nil { dfs(a, b, p.son[u]) }
		}
	}
	g[x][y] = t
}

func insert(word string, id int) {
	p := root
	for _, c := range word {
		u := c - 'a'
		if p.son[u] == nil { p.son[u] = Constructor() }
		p = p.son[u]
	}
	p.id = id
}

func main() {

	board := [][]byte{
		{'o', 'a', 'a', 'n'},
		{'e', 't', 'a', 'e'},
		{'i', 'h', 'k', 'r'},
		{'i', 'f', 'l', 'v'},
	}
	words := []string{"oath", "pea", "eat", "rain"}
	fmt.Println(findWords(board, words))  // [oath eat]
}
